package com.jacklei.KMP;

//KMP算法
public class KMP {

    public static void main(String[] args) {
        String s = "abcsdsabcdaedhjsdanazczbadgajyacbdxd";
        String target= "abcsabced";
        System.out.println(KMP(s, target));
        System.out.println(traditional(s, target));
    }

    public static  int traditional(String s,String target){
        char[] targetChars = target.toCharArray();
        char[] chars = s.toCharArray();
        int result = 0;
        int current = 0;
        int i = 0;
        int j = 0;
        while (i < targetChars.length){
            if (chars[i] == targetChars[j]) {
                i++;
                j++;
                current ++;
                //result = Math.max(current, result);
            }else {
                result = Math.max(current, result);
                current = 0;
                i++;
                j=0;
            }
        }
        return Math.max(current, result);
    }

    public static int KMP(String s,String target){
        if(s.isEmpty()|| target.isEmpty())return -1;

        char[] targetChars = target.toCharArray();
        char[] chars = s.toCharArray();
        //1.得到next数字
        int[] next = getNextArray(targetChars);
        //2进行匹配
        int result = 0;
        int current = 0;
        int i = 0;
        int j = 0;
        while (i < chars.length){
            if (chars[i] == targetChars[j]) {
                i++;
                j++;
                current++;
               // result = Math.max(current, result);
            }else {
                if(next[j] == -1){
                    i++;
                    result = Math.max(result,current);
                    current = 0;
                }else j = next[j];
            }
        }
        return Math.max(current, result);
    }

    private static int[] getNextArray(char[] target) {
        int[] next = new int[target.length];
        //人为规定的 next 的第一个为 -1;
        next[0] = -1;
        //人为规定的 ： 前面字符串 至于自身完全匹配 标记为0;
        next[1] = 0;
        int i = 2;
        while (i < next.length ){
            if(next[i-1] > 0 ) {
                if(target[next[i-1]] == target[i-1]){
                    next[i] = next[i-1]+1;
                    i++;
                    continue;
                }
            }
                next[i] = target[0] == target[i - 1] ? 1 : 0;
                i++;
        }
        return next;
    }
}
